{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Two Sum 两数之和\n",
    "\n",
    "## 题目：\n",
    "\n",
    " - https://leetcode.com/problems/two-sum/\n",
    " - https://leetcode-cn.com/problems/two-sum/description/\n",
    "\n",
    "```\n",
    "给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。\n",
    "\n",
    "你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。\n",
    "\n",
    "> 示例：\n",
    "\n",
    "给定 nums = [2, 7, 11, 15], target = 9\n",
    "\n",
    "因为 nums[0] + nums[1] = 2 + 7 = 9\n",
    "所以返回 [0, 1]\n",
    "```\n",
    "\n",
    "## 难度：Easy\n",
    "\n",
    "这个题目略微有点简单，我们只要注意的是，同样的元素不能被重复利用两次。\n",
    "\n",
    "还有就是思考，是不是我们可以使用一次循环就能够找到这两个数呢？\n",
    "\n",
    "接下来我们看一下如何解决这个问题。\n",
    "\n",
    "> 思路 1\n",
    "\n",
    " - 简单判断一下，是否两个数都在 list 中，以及判断两个数不是重复利用一个元素即可。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # 循环名为 nums 的 list\n",
    "        for num_one in nums:\n",
    "            # 判断 target 减去 num_one 是否仍在我们的 nums list 中，另一个条件是这两个数不是同一个元素\n",
    "            if target - num_one in nums and num_one is not target-num_one:\n",
    "                # 返回两个数对应的 index\n",
    "                return [nums.index(num_one), nums.index(target - num_one)]\n",
    "            \n",
    "nums = [4, 3, 5, 15]\n",
    "target = 8\n",
    "s = Solution()\n",
    "print(s.twoSum(nums, target))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 思路 2\n",
    "\n",
    " - 其实我们上一个解决方案已经是弄的一个 for 循环了，这次我们换一个思路。\n",
    " - 可以用 $O(n^2)$ 的循环（lookup）\n",
    " - 其实也可以牺牲空间换取时间，异常聪明的 AC 解法\n",
    " \n",
    "```\n",
    "    2     7      11    15\n",
    "    不存在 存在之中  \n",
    "lookup {2:0} [0, 1]\n",
    "```\n",
    "大体思路如下：\n",
    "\n",
    " - 建立字典 lookup 存放第一个数字，并存放该数字的 index\n",
    " - 判断 lookup 中是否存在： target - 当前数字， 则表面 当前值和 lookup中的值加和为 target\n",
    " - 如果存在，则返回： target - 当前数字 的 index 和 当前值的 index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # 创建 lookup 字典\n",
    "        lookup = {}\n",
    "        # 使用 enumerate 语法，返回的是每一个元素及其对应的 index\n",
    "        for i, num in enumerate(nums):\n",
    "            if target - num in lookup:\n",
    "                return [lookup[target - num],i]\n",
    "            lookup[num] = i\n",
    "        return []\n",
    "    \n",
    "nums = [4, 3, 5, 15]\n",
    "target = 8\n",
    "s = Solution()\n",
    "print(s.twoSum(nums, target))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 思路 3\n",
    "\n",
    " - 对于 dict ，也就是其他语言的 map，判断一个元素在不在容器中，list 要遍历，而 set 和 dict 直接根据哈希算出，不需要遍历\n",
    " - 我们可以仿照上面的代码，但是换个简单的写法。\n",
    " - 对于字典的这种方式，如果我们只是判断 i 以及 target - i 是不是相等，这样是错误的，如果两个元素相同，但是不是同一个元素，那就会出错了。\n",
    " \n",
    "比如，我们先看一下错误的版本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dict1 = {}\n",
    "        for k, i in enumerate(nums):\n",
    "            dict1[i] = k\n",
    "            if target - i in dict1 and i is not target - i:\n",
    "                return [dict1[target - i], dict1[i]]\n",
    "\n",
    "nums = [3, 3]\n",
    "target = 6\n",
    "s = Solution()\n",
    "print(s.twoSum(nums, target))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的代码是存在问题的，对于相同的元素 [3, 3]， target =6， 就得到了 None ，按理说，应该得到 [0, 1] 的。所以，这地方的判断是错误的。\n",
    "\n",
    " - 对于字典的那种方式,就只能索引为 key,数据为value,只是这样一来,判断在或者不在,还是多了一层循环\n",
    " \n",
    "下面的版本是正确的版本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        for k, i in enumerate(nums):\n",
    "            if target - i in nums[k + 1:]:\n",
    "                return [k, nums[k + 1:].index(target - i) + k + 1]\n",
    "\n",
    "nums = [3, 3]\n",
    "target = 6\n",
    "s = Solution()\n",
    "print(s.twoSum(nums, target))       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 小结\n",
    "\n",
    "应该还有更加好的解法，大佬们积极贡献自己的解法哈。一起为好的工作，好的未来，加油。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
